package com.xw.class05;

/**
 * @author: xw
 * @create: 2022/9/29 15:28
 * @description: 快速排序与荷兰国旗
 */
public class Code02_PartitionAndQuickSort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * arr[L..R]上，以arr[R]位置的数做划分值, <= x的放左边, >X的放右边
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int partition(int[] arr, int L, int R) {
        if(L > R){
            return -1;
        }
        if(L == R){
            return L;
        }
        int lessEquals = L -1;
        int index = L;
        while(index < R){
            if(arr[index] <= arr[R]){
                swap(arr,index,++lessEquals);
            }
            index++;
        }
        swap(arr,++lessEquals,R);
        return lessEquals;
    }

    /**
     *  arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
     * 	 分为三部分 <arr[R]     ==arr[R]    > arr[R]
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int[] netherlandsFlag(int[] arr, int L, int R){
        if (L > R) {
            return new int[] { -1, -1 };
        }
        if (L == R) {
            return new int[] { L, R };
        }
        // < 区 右边界
        int less = L - 1;
        // > 区 左边界
        int more = R;
        int index = L;
        while(index < more){
            if(arr[index] == arr[R]){
                index++;
            }else if(arr[index] < arr[R]){
                swap(arr,++less,index++);
            }else{
                swap(arr,--more,index);
            }
        }
        swap(arr,R,more);
        return new int[]{less+1,more};
    }

    public static void quickSort01(int[] arr){
        if(null == arr || arr.length == 0){
            return;
        }
        process(arr,0,arr.length-1);
    }

    private static void process(int[] arr, int left, int right) {
        int M = partition(arr, left, right);
        process(arr,left,M-1);
        process(arr,M+1,right);
    }

    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    // arr[L...R] 排有序，快排2.0方式
    public static void process2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // [ equalArea[0]  ,  equalArea[0]]
        int[] equalArea = netherlandsFlag(arr, L, R);
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }
    
    public static void quickSort3(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        process3(arr, 0, arr.length - 1);
    }

    private static void process3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        // [ equalArea[0]  ,  equalArea[0]]
        int[] equalArea = netherlandsFlag(arr, L, R);
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }


}
